package org.example.myleet.p725;

import org.example.myleet.Utils.ListNode;

public class Solution {
    public ListNode[] splitListToParts(ListNode head, int k) {
        ListNode[] result = new ListNode[k];
        //先第一次遍历得到链表长度
        int n = 0;
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode cur = dummy;
        while (cur.next != null) {
            cur = cur.next;
            ++n;
        }
        //计算被分隔后每部分链表的长度
        int len = n / k;
        //计算前多少个链表需要多一个节点长度
        int remain = n % k;
        cur = dummy.next;
        for (int i = 0; i < k; ++i) {
            ListNode newDummy = new ListNode(-1);
            ListNode newCur = newDummy;
            for (int j = 0; j < len; ++j) {
                //处理每部分链表的长度
                newCur.next = cur;
                newCur = newCur.next;
                cur = cur.next;
            }
            if (i < remain) {
                //前remain个，需要多一个节点的长度
                newCur.next = cur;
                newCur = newCur.next;
                cur = cur.next;
            }
            //完成一部分链表分隔，截断，并放入结果中
            newCur.next = null;
            result[i] = newDummy.next;
        }
        return result;
    }
}
